package com.formula.datastructure.exercise.tree;

import com.formula.datastructure.util.DataUtil;

/**
 * ADT:
 * insertNode
 * search
 * traverse
 * deleteNode - 只有删除放在tree里面操作
 */
public class BinSearchTree {
    private BinSearchNode root;

    public BinSearchTree() {

    }

    public void insertNode(Integer input) {
        BinSearchNode newNode = new BinSearchNode(input);
        if (root == null) {
            root = newNode;
        } else {
            root.insert(newNode);
        }
    }

    public void deleteNode(Integer input) {
        /**
         * 首先记住3个变量声明
         */
        BinSearchNode target = root;
        BinSearchNode targetParent = root;
        boolean isLeft = false;

        /**
         * 用while找到target和parent
         *
         * 找不到就要退出
         */
        while (target.data != input) {
            targetParent = target;
            if (input < target.data) {
                isLeft = true;
                target = target.left;
            } else if (input > target.data) {
                isLeft = false;
                target = target.right;
            }
            if (target == null) {
                return;
            }
        }

        // 找出来的target开始判断
        if (target.left == null && target.right == null) {
            if (isLeft) {
                targetParent.left = null;
            } else {
                targetParent.right = null;
            }
        } else if (target.left != null && target.right != null) {
            BinSearchNode successor = target.right;
            BinSearchNode successorParent = target;
            // 找出successor
            while (successor.left != null) {
                successorParent = successor;
                successor = successor.left;
            }

            // 中序遍历的下一个就是自己的右子树
            if (successor == target.right) {
                // 先把左子树分配了
                successor.left = target.left;
                if (isLeft) {
                    targetParent.left = successor;
                } else {
                    targetParent.right = successor;
                }
            } else {
                // successor绝对没有左子树
                successorParent.left = successor.right;
                target.data = successor.data;
            }
        } else if (target.left == null) {
            if (isLeft) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        } else {
            if (isLeft) {
                targetParent.left = target.left;
            } else {
                targetParent.right = target.left;
            }
        }

    }

    public void inOrderTraverse() {
        if (root != null) {
            root.inOrderTraverse();
        }
    }

    public static void main(String[] args) {
        BinSearchTree tree = new BinSearchTree();
        Integer[] array = DataUtil.genUniqueArray(20, 100);
        for (Integer item : array) {
            tree.insertNode(item);
        }
        tree.inOrderTraverse();
        System.out.println(array[5] + " : " + array[10] + " : " + array[15]);
        tree.deleteNode(array[5]);
        tree.deleteNode(array[10]);
        tree.deleteNode(array[15]);
        tree.inOrderTraverse();
    }
}
